/*
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。

返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。

 

示例 1：

输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
示例 2：

输入：s = "baaca", k = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。
 

提示：

1 <= k <= S.length <= 1000
s 只由小写字母组成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/orderly-queue
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

using namespace std;

// 分类讨论
class Solution {
public:
    string orderlyQueue(string s, int k) {
        string res{s};
        if (k == 1) {
            int n = s.size();
            for (int i = 1; i < n; ++i) {
                char c = s[0];
                s = s.substr(1);
                s += c;
                if (s < res) {
                    res = s;
                }
            }
        } else {
            // 当 k > 2 时，一定能够将 s 移动成 升序字符串。
            sort(res.begin(), res.end());
        }
        return res;
    }
};
